package net.projecteuler.prob;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

import net.projecteuler.util.DigitUtil;

public class Problem62 implements Runnable {

	private static final int MAX = 10000;
	private Comparator<long[][]> comparator = new Comparator<long[][]>() {
		@Override
		public int compare(long[][] aa1, long[][] aa2) {
			long[] o1 = aa1[1];
			long[] o2 = aa2[1];
			if(o1.length > o2.length)
				return 1;
			else if(o1.length < o2.length)
				return -1;
			else{
				for(int i = 0; i < o1.length; i++){
					if(o1[i] > o2[i])
						return 1;
					if(o1[i] < o2[i])
						return -1;
				}
			}
			
			return 0;
		}
	}; 
	
	@Override
	public void run() {
		long[][][] cubeDigits = new long[MAX][2][];
		
		for(int i = 0; i < MAX; i++){
			cubeDigits[i][0] = new long[]{i};
			List<Long> digitList = new ArrayList<Long>();
			long cube = (long)i * (long)i * (long)i;
			while(true){
				digitList.add(cube % 10);
				cube /= 10;
				if(cube == 0)
					break;
			}
			cubeDigits[i][1] = new long[digitList.size()];
			for(int j = 0; j < digitList.size(); j++)
				cubeDigits[i][1][j] = digitList.get(j);
			Arrays.sort(cubeDigits[i][1]);
		}
		Arrays.sort(cubeDigits, comparator);
		
		int cnt = 1;
		for(int i = 1; i < MAX; i++){
			if(compareDigitArr(cubeDigits[i-1][1], cubeDigits[i][1])){
				cnt++;
			} else {
				if(cnt >= 3){
					String str = cnt + " :";
					for(int j = 0; j < cnt; j++){
						str += " " + cubeDigits[i-1-j][0][0];
					}
					System.out.println(str);
				}
				cnt = 1;
			}
		}
		
		
	}
	
	private boolean compareDigitArr(long[] arr1, long[] arr2){
		if(arr1.length != arr2.length)
			return false;
		
		for(int i = 0; i < arr1.length; i++)
			if(arr1[i] != arr2[i])
				return false;
		
		return true;
	}

}

